Squares of a Sorted Array
Leetcode #977 | Easy | Два указателя | Указатель на запись
Идея
Два указателя - один с конца другой с начала (идея в том что большие квадраты по краям). Дальше бежим по циклу указателем write с конца и заполняем с конца, то есть большими числами (сравниваем их по абсолютной величине)
Big-O
- Время
O(N) - Память
O(N)
Код
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int l = 0, r = n - 1;
for (int w = n - 1; w >= 0; w--) {
if (Math.abs(nums[l]) > Math.abs(nums[r])) { res[w] = nums[l] * nums[l]; l++; }
else { res[w] = nums[r] * nums[r]; r--; }
}
return res;
}
}